package j2024.j202408;

public class j0820 {
    /**
     * 44. 通配符匹配
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch1(String s, String p) {
        int m = s.length();
        int n  = p.length();
        s = " "+s;p = " "+p;

        char[] str = s.toCharArray();
        char[] ptr = p.toCharArray();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if(ptr[j]=='*'){
                dp[0][j] = true;
            }else {
                break;
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(ptr[j]=='*'){
                    dp[i][j] = dp[i-1][j]||dp[i][j-1];
                }else {
                    dp[i][j] = (ptr[j]=='?'||ptr[j]==str[i]) && dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }

    /**
     * 10. 正则表达式匹配
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        s = " "+s;
        p = " "+p;
        char[] str = s.toCharArray();
        char[] ptr = p.toCharArray();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for (int i = 2; i <= n; i+=2) {
            if(ptr[i]=='*')dp[0][i] = true;
            else break;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(ptr[j]=='*'){
                    dp[i][j] = dp[i][j-2]||(ptr[j-1]=='.'||ptr[j-1]==str[i])&&dp[i-1][j];
                }else {
                    dp[i][j]=(ptr[j]=='.'||ptr[j]==str[i])&&dp[i-1][j-1];
                }
            }
        }
        return  dp[m][n];
    }

    /**
     97. 交错字符串
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if(m+n!=s3.length()){
            return false;
        }
        s1 = " "+s1;s2 = " "+s2;s3 = " "+s3;
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            if(s2.charAt(i)==s3.charAt(i))dp[0][i] =true;
            else break;
        }
        for (int i = 1; i <= m; i++) {
            if(s1.charAt(i)==s3.charAt(i))dp[i][0] =true;
            else break;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = (s1.charAt(i)==s3.charAt(i+j) && dp[i-1][j])||(s2.charAt(j)==s3.charAt(i+j) && dp[i][j-1]);
            }
        }
        return dp[m][n];
    }

    /**
     * 712. 两个字符串的最小ASCII删除和
     * @param s1
     * @param s2
     * @return
     */
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+ s1.charAt(i-1));
                }
            }
        }
        int sum = 0;
        for(char ch:s1.toCharArray())sum+=ch;
        for(char ch:s2.toCharArray())sum+=ch;
        return sum-dp[m][n]-dp[m][n];

    }
}
